1. Field of the Invention
This invention relates generally to communication networks and, more particularly, to routing algorithms for ad-hoc networks, such as, for example, a multi-hop or a low rate-wireless personal area network (LR-WPAN). The invention also relates to methods of routing communications in a communication network, such as an ad-hoc network.
2. Background Information
The ubiquitous nature of wireless sensor networks (WSNs) in industrial, commercial and residential applications has brought new research challenges in this domain. Among these challenges is an efficient routing scheme suited for low rate WSNs.
The advent of WSNs promises to spread the usage of inexpensive sensing technology in a wide variety of application domains. For example, industrial, commercial and residential areas are quick to adopt that technology. These application domains demand that underlying ad hoc networking technology is self-configurable, scalable and robust. Typically, these applications do not require a relatively large data bandwidth.
The market interest and potential of WSN technology can be judged from many active consortia and standards groups to promote its commercial use. These include, for example, IEEE 802.15.4, Zigbee Alliance and WINA. Most recently, there is formation of a 6Lo WPAN working group under the auspices of IETF.
The sensor networks strive to meet a minimum quality of service specific to the application domain with varying tolerable degrees of message delivery latency and reliability. Many message routing schemes have been proposed for these sensor networks that meet specific quality of service requirements. See, e.g., Lundberg, D., “Ad hoc protocol evaluation and experiences of real world ad hoc networking,” Tech. Rep., Department of Information Technology, Uppsala University, 2002, which provides an overview of these routing proposals. Contrary to the perception, many of these routing schemes are difficult to implement in a low-end 8-bit microprocessor with limited memory and processing power. Maintaining the relatively low cost of these sensing devices is the fundamental premise for rapid field adoption. Often, adequate range of sensing coverage cannot be achieved due to a limitation in the number of message hops permitted under a routing scheme. Disproportionately large routing control message overhead also causes poor message latency and throughput in the sensing network.
The lack of an adequate formal analytical framework to specify, verify and guarantee network performance for WSN is proving to be a bottleneck for larger user acceptance. There has been a relatively large body of research work on routing algorithms in other areas, such as, for example, Internet routing protocols. Some of these techniques are based on formal theoretical foundations. See, e.g., Daescu, O., et al., “Gara: A geometry aided routing algorithm,” 2004 Workshop on High Performance Switching and Routing, 2004, pp. 224-28 (geometric computing); West, D., Introduction To Graph Theory, Prentice Hall, second edition, 2001 (graph theory); and Kurose, J., et al., Computer Networking: A top-Down Approach Featuring the Internet, Addison Wesley, second edition, 2003 (use of Bellman Ford and Dijkstra's algorithms for Internet routing protocols).
Sensor networks, however, differ from Internet-like broadband networks in many fronts. These networks can handle much lower data rates, typically up to about 250 Kbps. They can tolerate very little routing overhead and need to guarantee better message delivery latency and reliability. In some cases, the nodes in the network are either fully mobile or semi-mobile in the sense that only a small subset of nodes may move around infrequently. Finally, the implementation of the routing protocol should require minimal computing resources. As a result of these differences, it is believed that existing Internet routing strategies cannot be directly applied to sensor networks.
Dijkstra's algorithm solves the single-source shortest path problem for a directed graph with nonnegative edge weights. For example, if the vertices of the graph represent cities and edge weights represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between two cities. The input of the algorithm consists of a weighted directed graph G and a source vertex s in graph G. Set V is the set of all vertices in the graph G. Each edge of the graph is an ordered pair of vertices (u,v) representing a connection from vertex u to vertex v. The set of all edges is denoted as set E. Weights of edges are given by a weight function w: E->[0, ∞]; therefore, w(u,v) is the non-negative cost of moving from vertex u to vertex v. The cost of an edge can be thought of as, or a generalization of, the distance between those two vertices. The cost of a path between two vertices is the sum of costs of the edges in that path. For a given pair of vertices s and t in V, the algorithm finds the path from s to t with lowest cost (i.e., the shortest path). It can also be used for finding costs of shortest paths from a single vertex s to all other vertices in the graph.
Proactive Source Routing (PSR) is a relatively very simple routing protocol designed specifically for mesh networking that can be implemented in a low-cost sensor node. See U.S. Patent Application Publication No. 2004/0233855. PSR is designed to provide a very simple and efficient routing mechanism that can be implemented in an 8-bit embedded processor. In a PSR architecture, one node in the sensor network is designated and acts as a network coordinator (NC). In IEEE 802.15.4 parlance, the NC is the Pan Coordinator of the network. A message from a non-NC node, called a network device (ND), is typically directed to the NC. The NC, in turn, forwards the message to the destination ND.
In the PSR architecture, when a new node is powered up, it broadcasts a beacon request. A node that has already joined the network and is located within the radio range of the beaconing device, receives the beacon request. This member node has previously gone through a similar discovery cycle to join the network. As a result, it has learned its routing information to send and receive messages from the NC. Upon receiving the beacon request, it may choose to respond by sending its identity or address to the beaconing node. The new node collects beacon responses from one or more such willing member nodes. It stores the address along with a cost indicator for each of these neighbor member in its local routing table. The cost indicator represents the current link quality of the communication link between the new node and the corresponding neighbor member node. Note that this cost (i.e., the local link cost) is an indicator local to the communication between the pair of nodes only.
As shown in FIG. 1A, if a new member ND A wants to send a message to another member ND B, in PSR, this is accomplished by ND A sending an upstream message to the NC. Upon receiving the message, the NC forwards it to the requested destination ND B as a downstream message as shown in FIG. 1B.
To initiate sending the upstream message, ND A looks in its local routing table to select the neighbor with the minimum current local link cost. ND A first attempts to send the message to this minimum local link cost neighbor, say ND C. Upon receipt of this message, ND C (a relay node) follows a similar neighbor selection using its own routing table to forward the message to another ND. Before it does that, ND C adds its own address to the message as part of the routing specification. This process continues until the message reaches the NC. Along the way, each relay node adds its own address to the message routing specification.
The NC, upon receiving the message, extracts and saves the routing specification which is the route that the message from ND A followed to the NC. In other words, the NC stores the sequence of intermediate relay node addresses as the route for ND A. Anytime, the NC needs to send a downstream message to an ND, such as ND A, it will copy this previously learned route in reverse order of addresses as the downstream routing specification as shown in FIG. 1B. As the message traverses downstream towards ND A, each relay node will remove its own address from the routing specification. It also determines the next node that the message is to be relayed to from this specification.
The above routing scheme is simple to implement and works well for relatively small networks. Each node sends the message to a known neighbor based on a current local cost indicator. If the message fails to be delivered to the neighbor after a fair number of retrials, then the node selects the next minimum link cost local neighbor.
However, PSR is suboptimal in the sense that it follows the route that is deemed to be optimum locally. With this local approach, a message sometimes will take a globally suboptimal route, possibly taking a greater count of “hops” than is necessary. This has the potential to add extra delays and to decrease the probability of final message delivery. PSR also requires the routing specification to be incrementally added in upstream routing which limits the number of hops that a message can take to arrive at the NC. More significantly, it is required to send this routing specification which is purely routing overhead.
Using the PSR approach, since the NC receives and saves the complete routing specifications from each ND, it needs a relatively large memory for storing that data. Even worse, there is a relatively large amount of redundant information in the routing specification coming from the different NDs. Although this redundancy can be removed by intelligent software filtering, there is, nevertheless, an increased address overhead that provides an opportunity for improvement.
Accordingly, there is room for improvement in ad-hoc networks and methods for routing packets in such networks.